package c.footstep;

import java.util.HashMap;
import java.util.Map;

public class TestMainNew {
	
	public static void main(String[] args){
	  int size=45;	
	  map.put(1,1);map.put(2,2);
	  int result=fun(size);	
	  System.out.println(result);	
	}
	
static Map<Integer,Integer> map=new HashMap<Integer,Integer>();
	public static int fun(int size){	
	  if(map.get(size)!=null){
		  return map.get(size);
	  }	
	  int total=fun(size-1)+fun(size-2);
	  map.put(size,total);
	  return total;
	}
}
